﻿//https://leetcode.cn/problems/fibonacci-number/

class Solution {
    int memo[31];
public:
    int fib(int n)
    {
        memset(memo, -1, sizeof memo);
        return dfs(n);

    }

    int dfs(int n)
    {
        //每次进入递归函数前先检查是否已被计算过
        if (memo[n] != -1)
        {
            return memo[n];
        }

        //递归函数出口
        if (n == 0 || n == 1)
        {
            memo[n] = n;  //计算的值加入备忘录
            return n;
        }

        //函数体
        memo[n] = dfs(n - 1) + dfs(n - 2);  //计算的值加入备忘录
        return memo[n];

    }
};
